package org.example.Soution001;

import java.util.LinkedList;
import java.util.Queue;

public class Ancestor {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(37);
        root.left = new TreeNode(-34);
        root.right = new TreeNode(-48);
        root.left.right = new TreeNode(-100);
        root.right.left = new TreeNode(-101);
        root.right.right = new TreeNode(48);
        root.right.right.left = new TreeNode(-54);
        root.right.right.left.left = new TreeNode(-71);
        root.right.right.left.right = new TreeNode(-22);
        root.right.right.left.right.right = new TreeNode(8);
        Ancestor ancestor = new Ancestor();
        System.out.println(ancestor.lowestCommonAncestor(root,root.right.right.left.left,root.right.right).val);

    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //后序遍历，对树进行剪枝，若某一枝上不存在p和q，则剪除
        //题目中已知p q必存在于树中
        cutBranch(root,p,q);
        //从root开始遍历，找到第一个有左右孩子的节点返回
        TreeNode result=root;
        while(result!=null){
            if(result==p||result==q||(result.left!=null&& result.right!=null)){
                return result;
            }else if(result.left==null){
                result=result.right;
            }else{
                result=result.left;
            }
        }
        return null;
    }

    public boolean cutBranch(TreeNode root, TreeNode p, TreeNode q) {
        //后序遍历
        boolean left=root.left!=null?cutBranch(root.left,p,q):true;
        boolean right=root.right!=null?cutBranch(root.right,p,q):true;
        if (root.left != null&&left) {
            root.left =null;
        }
        if (root.right != null&&right) {
            root.right =null;
        }
        if(root==p||root==q||!left||!right){
            return false;
        }
        return true;
    }
}
